from collections import defaultdict
from typing import List


class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [defaultdict(lambda: 0) for _ in range(n)]
        ans = 0
        for i in range(1, n):
            for j in range(i):
                re = (nums[i] + nums[j]) % k
                dp[i][re] = max(dp[i][re], dp[j][re] + 1)
                ans = max(ans, dp[i][re])
        return ans


if __name__ == '__main__':
    s = Solution()
    r = s.maximumLength(nums=[1, 2, 3, 4, 5], k=2)
    print(r)
